package com.c2b.algorithm.newcoder.dynamic_programming;

/**
 * <a href="https://www.nowcoder.com/practice/6fe0302a058a4e4a834ee44af88435c7?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj">最小花费爬楼梯</a>
 * 给定一个整数数组cost，其中cost[i]  是从楼梯第i个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。<br>
 * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。<br>
 * 请你计算并返回达到楼梯顶部的最低花费。<br>
 * <p>
 * 数据范围：数组长度满足1≤n≤10^5，数组中的值满足1≤cost[i]≤10^4
 *
 * @author c2b
 * @since 2023/3/15 10:39
 */
public class BM0064MinCostClimbingStairs_S {

    public int minCostClimbingStairs(int[] cost) {
        // 楼梯总台阶数量
        final int length = cost.length;
        final int[] dp = new int[length + 1];
        // 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯==》隐藏条件：dp[0]、dp[1]均为0
        for (int i = 3; i <= length; i++) {
            // 走上第i个楼梯 = (第i - 2个楼梯走2个楼梯 和 第i - 1个楼梯走1个楼梯)的最小值决定
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[length];
    }

    public static void main(String[] args) {
        BM0064MinCostClimbingStairs_S bm0064MinCostClimbingStairs_s = new BM0064MinCostClimbingStairs_S();
        System.out.println(bm0064MinCostClimbingStairs_s.minCostClimbingStairs(new int[]{2, 5, 20}));
    }
}
